package com.github.hgkmail.hello.leetcode101.firstsearch;

import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;

//BFS一般用于解决[最短路径]问题，因为广度优先是不断[扩大]，搜到时扩大的层数 level 就是最短路径。
//先用DFS找出第一座岛屿，并用2表示，然后用BFS找另一座岛屿，找到时就是最短路径。
public class LC934ShortestBridge {

    public int shortestBridge(int[][] grid) {
        //base case
        if (grid.length<=0 || grid[0].length<=0) {
            return 0;
        }
        int[][] visited = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                visited[i][j]=0;
            }
        }
        //使用dfs找出第一个岛屿，并用2表示
        boolean findFirst = false;
        Queue<int[]> queue = new ArrayDeque<>(grid.length*grid[0].length);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                findFirst = dfs(grid, visited, i, j, queue) > 0;
                if (findFirst) break;
            }
            if (findFirst) break; //用标志变量+2个break，跳出双重循环
        }

        //使用bfs找出第2个岛屿，并记录最短距离
        int level=-1; //搜索扩大的层数，即最短路径，第一层点是岛屿，因此初始值为-1
        int x,y;
        int[] directions = new int[]{-1,0,1,0,-1};
        while (!queue.isEmpty()) {
            int len = queue.size(); //取出一层的点
            level+=1;
            while (len>0) {
                int[] xy = queue.poll();
                len-=1;
                for (int i = 0; i < 4; i++) {
                    x=xy[0]+directions[i];
                    y=xy[1]+directions[i+1];
                    if (x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y]==2) {
                        continue;
                    }
                    if (grid[x][y]==1) {
                        return level;
                    }
                    //把0的点变成2，避免重复搜索（这里用visited也可以，用'2'可以省一个数组）
                    grid[x][y]=2;
                    queue.offer(new int[]{x,y});
                }
            }//while
        }

        return level;
    }

    public int dfs(int[][] grid, int[][] visited, int i, int j, Queue<int[]> queue) {
        if (i<0 || i>=grid.length || j<0 || j>=grid[0].length || visited[i][j]==1) {
            return 0;
        }
        visited[i][j]=1;
        if (grid[i][j]==0) {
            return 0;
        }
        grid[i][j]=2;
        queue.offer(new int[]{i, j}); //把岛屿的点入队，用于后面的BFS
        int area=1;
        int[] directions = new int[]{-1,0,1,0,-1};
        for (int k = 0; k < 4; k++) {
            int x=i+directions[k];
            int y=j+directions[k+1];
            area += dfs(grid, visited, x, y, queue);
        }
        return area;
    }

    public static void main(String[] args) {
//        int[][] grid = new int[][]{{1,1,1,1,1},{1,0,0,0,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}};
        int[][] grid = new int[][]{{0,1,0},{0,0,0},{0,0,1}};
        int[][] visited = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                visited[i][j]=0;
            }
        }
        System.out.println(new LC934ShortestBridge().shortestBridge(grid));
    }
}
